1. Field of the Invention
The present invention relates to a detection apparatus, a detection method and a computer program. More specifically, the present invention relates to a detection apparatus, a detection method and a computer program for detecting a cut change at high accuracy.
2. Description of the Related Art
Process of detecting a cut change from image is useful in analysis, encryption, and search of the image.
A “cut” here means a chunk of image (image clip) continuous in space, and the cut change means a concatenation point between cuts, namely, a border where discontinuous image clips are concatenated.
The cut change is also referred to as a shot change, a scene change, or an image change point. In this specification, the term “cut change” is used.
Available as cut change detection methods are the statistical difference method, the pixel difference method, the encoding data method, the edge method, etc. The histogram difference method is known as the most precise cut change detection method.
The histogram difference method uses a difference between histograms.
The histogram is a distribution of luminance or color of an image and is generated by casing ballots into bins into bins according to gradations of luminance or color of each pixel (16 to 64 gradations are widely used). The distribution of the frequency occurrence of luminance or color of the image is thus determined.
The histogram difference method is divided into a simple histogram difference method and a segmentation histogram difference method.
The simple histogram difference method calculates as an evaluation value a difference between histograms of images of two frames to be processed (as disclosed in Transactions of Information Processing Society of Japan Vol. 33, No. 4, pp. 543-550 by Akio NAGASAKA and Yuzuru TANAKA).
In the simple histogram difference method, the sum of absolute values of differences between the corresponding bins of histograms (hereinafter referred to as histogram difference absolute sum) is calculated as an evaluation value.
In the segmentation histogram difference method, the entire image of each of two frames is segmented into a predetermined number of blocks (for example, 16 blocks as disclosed in Transactions of Information Processing Society of Japan Vol. 33, No. 4, pp. 543-550 by Akio NAGASAKA and Yuzuru TANAKA), a difference between the histograms in each block is determined, and only a predetermined number of blocks from the smallest difference is used to calculate an evaluation value (disclosed in Transactions of Information Processing Society of Japan Vol. 33, No. 4, pp. 543-550 by Akio NAGASAKA and Yuzuru TANAKA and the paper entitled “Comparison of Video Short Boundary Detection Techniques,” John S. Boreczky, Lawrence A. Rowe, Storage and Retrieval for Image and Video Database (SPIE) (1996) pp. 170-179).
Changes in the cut of image include a change caused by a movement of the camera, a movement and change of the shape of a subject (hereinafter also referred to as position, posture and shape change), changes in aperture stop, color balance, brightness and color of the subject (hereinafter also referred to as brightness and color change), a change caused by an appearance of tickers, and appearance and disappearance of a quickly moving object (hereinafter also referred to as appearance triggered change).
If the histogram difference method is used, most of information relating to the shape and spatial position of a subject to be photographed is lost in the generation process of the histogram. Sensitivity to the position, posture and shape change most frequently taking place in the cut is controlled to a low level. Accuracy of the cut change detection using the histogram difference method is thus higher than that of another cut change detection method.
The loss of the information relating to the shape and spatial position of the subject to be photographed in the histogram difference method causes one side effect that sensitivity to the brightness and color change and the appearance-triggered change becomes unnecessarily high.
The paper entitled “Comparison of Video Short Boundary Detection Techniques,” John S. Boreczky, Lawrence A. Rowe, Storage and Retrieval for Image and Video Database (SPIE) (1996) pp. 170-179 states that from among the above-described cut detection methods, the histogram difference method provides the highest detection accuracy level, and that the simple histogram difference method provides a detection rate of 85% and the segmentation histogram difference method provides a detection rate of 90%.
The segmentation histogram difference method even with the high accuracy thereof fails to detect one out of ten cut changes, namely, misses one out of ten cut changes to be detected as a cut change or detects cut changes that are in fact not cut changes. Accuracy level reached is not sufficiently high.
With reference to FIGS. 1A and 1B and FIGS. 2A and 2B, a relationship between a change in an image in a cut and histogram is discussed in conjunction with the histogram difference method.
FIGS. 1A and 1B illustrate changes in histogram with brightness level of an entire image changing.
As shown in FIGS. 1A and 1B, frame F1 and frame F2 are two frames to be processed and adjacent to each other in time. Histogram H1 and histogram H2 are luminance histograms of the entire images of the frame F1 and the frame F2, respectively.
As shown in FIGS. 1A and 1B, the shape and spatial position of a subject generally remain unchanged between the frame F1 and the frame F2. Luminance of the entire image is lowered. The histogram H2 is generally shifted leftward in comparison with the histogram H1 (to a lower luminance value).
A change in the image between the frame F1 and the frame F2 should be regarded as a change in the image in the cut. With the simple histogram difference method, if a difference between the histogram H1 and the histogram H2 becomes higher than a predetermined threshold, a point between the frame F1 and the frame F2 is likely to be erroneously as a cut change.
With the segmentation histogram difference method, if the luminance of the entire image changes, a change occurs between the frame F1 and the frame F2 in each histogram in all blocks, a cut change is also likely to be erroneously detected as a cut change.
FIGS. 2A and 2B illustrate histograms with a ticker appearing.
As shown in FIGS. 2A and 2B, frame F11 and frame F22 are two frames to be processed and adjacent to each other in time. Histogram H11 and histogram H12 are luminance histograms of the entire image of the frame F11 and the F12.
A change between the images of the frame F11 and the frame F12 in FIGS. 2A and 2B is mainly a suddenly emerging ticker. In comparison with the histogram H11, the histogram H12 includes a bin corresponding to a ticker area and excludes a bin corresponding to an area hidden by the ticker area.
The change between the images of the frame F11 and the frame F12 should be regarded as a change within a cut. If a difference between the histogram H11 and the histogram H12 becomes larger than a predetermined threshold with the simple histogram difference method, the switching point between the frame F11 and the frame F12 is likely to be erroneously detected as a cut change.
If the segmentation histogram difference method is used, a difference between the histograms of blocks other than the blocks of the ticker is small. If the number of blocks for use in the calculation of the evaluation value is small, a change between the images of the frame F11 and the frame F12 is identified to be no cut change. The change is less likely to be erroneously detected as a cut change.
In accordance with the segmentation histogram difference method, a predetermined number of blocks from the smallest difference between the histograms is used in the calculation of the evaluation value. Since the information relating to the shape and spatial position of the subject is partially used, cut change accuracy level is thus raised in comparison with the simple histogram difference method. If luminance of the entire image changes as shown in FIGS. 1A and 1B or if a subject moves at high speed across borders between blocks, the possibility of erroneous cut detection is heightened.
With the histogram difference method (the segmentation histogram difference method and the simple histogram difference method), a slight change in luminance can be erroneously detected as a cut change.
A relationship between the slight change in luminance and the histogram in the histogram difference method is described with reference to FIGS. 3 through 5A and 5B.
FIG. 3 illustrates a change in histograms in which a cut change is correctly detected.
As shown in FIG. 3, frames F31 through F33 shows a series of images consecutive in time. Starting with frame F31, two frames are successively processed at a time to detect a cut change. More specifically, frame F31 and frame F32 are processed, and then frame F32 and frame F33 are processed.
Histograms H31 through H33 are luminance histograms of the frames F31 through F33, respectively.
As shown in FIG. 3, a change between the images of the frame F31 and the frame F32 is mainly caused by a moving person as a subject. The distribution of the histogram H31 is substantially equal to the distribution of the histogram H32.
A histogram difference absolute sum between the histogram H31 and the histogram H32 is calculated as the difference between the histogram H31 and the histogram H32. The histogram difference absolute sum is sufficiently small. Since the difference between the histogram H31 and the histogram H32 is sufficiently small, the change between the frame F31 and the frame F32 is correctly identified as being not a cut change.
In contrast, the subject (person) in the frame F32 is quite different from a subject (mountain) in the frame F33. The histogram H32 is greatly different from the histogram H33.
The histogram difference absolute sum between the histogram H32 and the histogram H33 is calculated as the difference between the histogram H32 and the histogram H33. The histogram difference absolute sum becomes substantially large. Since the difference between the histogram H32 and the histogram H33 is sufficiently large, the difference between the frame F32 and the frame F33 is correctly identified as being a cut change.
FIG. 4 illustrates histograms in which a slight change takes place in luminance.
As shown in FIG. 4, frames F41 through F45 are a series of images consecutive in time. Starting with the frame F41, every two consecutive frames are processed to detect a cut change. First, the frame F41 and the frame F42 are processed, and then the frame F42 and the frame F43 are processed. Subsequently, every two consecutive frames are successively processed.
The histograms H41 through H45 are luminance histograms of the frames F41 through F45, respectively.
The frames F41 through F45 are monochrome images, and luminance of the entire image is uniform.
As shown in FIG. 4, the number of bins of the histogram is 64 and each bin has a width of four gradations. Bin borders are present between 76th gradation level and 77th gradation level, and between 80th gradation and 81st gradation, for example. The frames F41 through F45 have luminance values 73, 75, 77, 79 and 81 with slight changes in luminance taking place. Luminance of the entire image gradually increases. Since luminance of the entire image of each of the frames F41 through F45 remains unchanged, frequency of occurrence is concentrated in one bin in each of the histograms H41 through H45. A portion where frequency of occurrence is concentrated on a certain bin is referred to as a histogram peak.
Changes in the frames F41 through F45, namely, slight luminance changes are changes within the cut and not cut changes.
The frame F43 has luminance value 77 up slightly from luminance value 75 of the frame F42. Luminance of the entire image strides across the bin border between luminance value 76 and luminance value 77. In histogram H43, the histogram peak is shifted to the bin to the right of the bin of the histogram H42. The histogram difference absolute value between the histogram H42 and the histogram H43 becomes a maximum, and the switching point between the frame F42 and the frame F43 may be erroneously detected as a cut change.
The entire image of the frame F45 slightly increases in luminance to level 79 from level 81 in the frame F44. Luminance of the entire image rises beyond the bin border between luminance value 80 and luminance value 81. In the histogram H45, the histogram peak is shifted to the bin to the right of the bin in the histogram H44. The histogram difference absolute value between the histogram H44 and the histogram H45 becomes a maximum, and the switching point between the frame F44 and the frame F45 may be erroneously detected as a cut change.
A cut change is erroneously detected typically in the processing of the monochrome image. Even when a multi-color general image is processed, an erroneous detection is made if the histogram peak shifting across the bin border in response to a slight change in luminance or color causes a large change in the number of pixels of the bin. Along with the slight change in luminance or color between the two frames to be processed, variations between the histograms of the two images take place. This causes the detection accuracy of the cut change to be lowered.
Japanese Unexamined Patent Application Publication No. 2006-121274 has proposed one technique. In accordance with the disclosed technique, the average values of luminance of the entire two images are equalized so that the histograms of the two images are shifted along the axis of luminance (this process is hereinafter referred to as histogram shift). Subsequent to the histogram shift, a difference between the histograms is calculated. In accordance with this technique, the histograms have substantially the same shape and placed at the same location subsequent to the histogram shift. The variations between the histograms are canceled, and erroneous detection is controlled.
An erroneous detection can happen in such a case as shown in FIGS. 5A and 5B. FIGS. 5A and 5B illustrate a change in the histograms taking place when a slight change occurs in each of a left half and a right half of the image.
As shown in FIGS. 5A and 5B, frame F51 and frame F52 are two images consecutive in time. Histograms H51 and H52 are luminance histograms of the frame F51 and the frame F52, respectively.
The left half and the right half of each of the frame F51 and the frame F52 are monochrome images.
As shown in FIGS. 5A and 5B, the number of bins of the histogram is 64, and the bin width is four gradations. The bin borders may be between 76th gradation level and 77th gradation level and between 80th gradation level and 81st gradation level.
The luminance values of the left half and the right half of the frame F51 are 75 and 81, respectively. The luminance values of the left half and the right half of the frame F52 are 77 and 83, respectively. The frame F51 has histogram peaks in bins containing luminance value 75 and luminance value 81 and the frame F52 has histogram peaks in bins containing luminance value 77 and luminance value 83.
A change between the images of the frame F51 and the frame F52, namely, a slight change in luminance is a change within a cut. The border between the frame F51 and the frame F52 is not a cut change.
The left half of the frame F52 has a slight increase in luminance to luminance value 77 from luminance value 75 in the left half of the frame F51. The luminance of the left half of the image straddles across the bin border between luminance value 76 and luminance value 77. The right half of the frame F52 has a slight increase in luminance to luminance value 83 from luminance value 81 in the right half of the frame F51, but the luminance of the image does not straddle across bin border. Between the histogram 51 and the histogram 52, only the left histogram peak shifts across the bin border between luminance value 76 and luminance value 77 to the bin to the right thereof. As a result, if the histogram difference absolute sum between the histogram 51 and the histogram 52 reaches a predetermined threshold value, the change between the images of the frame F51 and the frame F52 is likely to be erroneously detected as a cut change.
If the shape of the histogram changes in response to a slight change in luminance, the histogram shift alone cannot cancel variations between the histograms. More specifically, if a change in image becomes more complex than the one shown in FIG. 4, the effectiveness of the histogram shift is lost.
Japanese Unexamined Patent Application Publication No. 2004-282318 discloses a technique of generating histograms. In accordance with the disclosed technique, ballots are cast into not only a corresponding bin but also in a bin next to the corresponding bin at a predetermined ratio.
Such a technique alleviates variations between histograms if variations of the entire image in luminance are small in comparison with the bin width of the histogram. If the variations of the entire image in luminance is not negligible with respect to the bin width, the variations between the histograms cannot be canceled by casting ballots into the adjacent bin.
The histogram difference method has difficulty reducing erroneous detection of cut change caused by a slight change in luminance or color.
Cut changes typically take place between adjacent images, and are called standard cut changes. In contrast, a cut change may take place when two cuts are concatenated within a mixture of a prior image and a subsequent image. Such a cut change is referred to as a blend cut change.
In the detection of the standard cut change, the similarity between the two images to be processed is calculated as an evaluation value. If similarity is lower than a predetermined threshold value, i.e., if non-similarity is higher than the predetermined threshold, the change between the two images is determined to be a cut change.
With this method, it is difficult to detect the blend cut change accurately. FIG. 6 illustrates a standard cut change. Frames F61 through F63 are a series of images consecutive in time. Starting with the frame F61, every two frames are processed to detect a cut change. More specifically, the frame F61 and the frame F62 are processed and then the frame F62 and the frame F63 are processed.
As shown in FIG. 6, the similarity between the frame F61 having a person as a subject and the frame F62 having a house as a subject is low. If the similarity is lower than a predetermined threshold, a change between the images of the frame F61 and the frame F62 is determined as a standard cut change. The similarity between the frame F62 having the house as a subject and the frame F63 having the house as a subject is high. If the similarity is higher than the predetermined threshold value, the change is determined to be not cut change.
FIG. 7 illustrates a blend cut change. As shown in FIG. 7, frames F71 through F73 are a series of images consecutive in time. Starting with the frame F71, every two consecutive images are processed. For example, the frame F71 and the frame F72 are processed, and then the frame F72 and the frame F73 are processed.
The frame F72 having a person and a house as subjects is a blend image of the frame F71 having the person as a subject and the frame F73 having the house as a subject. Two cuts are concatenated within the frame F72. The frame F72 is thus a blend cut change.
Such a blend cut change takes place when a cut change takes place between fields of the same image (hereinafter referred to as a field cut change), when consecutive images are blended through an image filter, when consecutive images are blended during encryption or decryption, or when consecutive images are blended during editing.
As shown in FIG. 7, the frame F72 contains portions similar to the frame F71 and the frame F73, and the frame F72 has high similarity with each of the frame F71 and the frame F73. The method of detecting cut change based on the similarity between the two consecutive images has difficulty detecting a blend cut change.
Japanese Unexamined Patent Application Publication No. 2000-295624 discloses a technique of detecting a field cut change as one of the blend cut changes. In accordance with the disclosed technique, a cut change is detected based on a similarity between two frames of every three frames with every second frame skipped rather than based on a similarity between two consecutive frames.
The technique disclosed in Japanese Unexamined Patent Application Publication No. 2000-295624 has difficulty detecting a cut change if an image in each frame quickly moves.
As shown in FIG. 8, frames F81 through F83 are a series of images consecutive in time and represent a scene in which a person goes away leftward from a house. The frames F81 through F83 show the person who quickly moves leftward on the screen. No cut change takes place.
As shown in FIG. 8, similarity between the frame F81 having the whole person image and a left portion of the house as subjects in the image thereof and the frame F82 having the whole person image and a larger left portion of the house as subjects in the image thereof is high. Similarity between the frame F82 and the frame F83 having a right half portion of the person image and a whole house image as subjects is high. Since the person quickly moves, similarity between the frame F81 having the whole person image and the left portion of the house as subjects in the image thereof and the frame F83 having the right half of the person image and the whole house image as subjects is low.
Cut change detection may be performed on the two frames (for example, frames F81 and F83) every three frames (frames F81 through F83) with every second frame (frame F82) skipped, in accordance with the technique disclosed in Japanese Unexamined Patent Application Publication No. 2000-295624. Since the similarity between the frame F81 and the frame F83 is low, the change throughout the frames F81 through F83 is likely to be erroneously identified as a blend cut change.
Japanese Unexamined Patent Application Publication No. 2002-64823 discloses a technique of a field cut change detection using encrypted data. However, this technique uses a feature quantity unique to an encrypted image of a particular encryption method, and is thus applicable to only an image that has been encrypted using that encryption method.
Japanese Unexamined Patent Application Publication No. 2000-324499 discloses another technique of detecting a cut change. The disclosed technique allows cut changes to be detected with a standard cut change and a field cut change differentiated from each other. In accordance with the disclosed technique, a difference between corresponding pixels on the two images to be processed is determined, the absolute values of the differences are summed (hereinafter referred to as difference absolute sum), and a difference between the sums of the difference absolute sums is determined. This technique still has difficulty detecting the blend cut changes (including the field cut change) at a high accuracy level.